package com.ayuer.chapter04;

import java.util.Arrays;
import java.util.LinkedList;

public class Infix2Suffix {
    public static void main(String[] args) {
        //中缀表达式转后缀
//        String token = "ab+";
//        String token = "a+b*c";
//        String token = "a*(b+c)";
        String token = "(a+b*c-d)*e";
        System.out.println(infixToPostfix(token));
//        Arrays.copyOfRange()
    }

    private static int priority(char op) {
        return switch (op) {
            case '(' -> 0;
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            default -> -1;
        };
    }

    private static String infixToPostfix(String token) {
        LinkedList<String> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < token.length(); i++) {
            char c = token.charAt(i);
            switch (c) {
                case '+', '-', '*', '/' -> {
                    //栈空直接入
                    if (stack.isEmpty()) {
                        stack.push(String.valueOf(c));
                    } else {
                        //运算符号
                        int currPriority = priority(c);
                        //与栈中比较优先级
                        String peekOp = stack.peek();
                        int peekOpPriority = priority(peekOp.charAt(0));
                        if (peekOpPriority >= currPriority) {
                            //出栈计算，将栈中大于等于出栈计算
                            while (!stack.isEmpty() && priority(stack.peek().charAt(0)) >= currPriority) {
                                //计算
                                sb.append(stack.pop());
                            }
                            //当前运算符入栈
                            stack.push(String.valueOf(c));
                        } else {
                            //优先级大入栈
                            stack.push(String.valueOf(c));
                        }
                    }
                }
                case '(' -> //左括号直接入栈
                        stack.push(String.valueOf(c));
                case ')' -> {
                    //出栈，直到遇到(结束
                    while (!stack.isEmpty() && stack.peek().charAt(0) != '(') {
                        sb.append(stack.pop());
                    }
                    //弹出(
                    stack.pop();
                }
                default -> {
                    //遇到字母数组就追加到sb中
                    sb.append(c);
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}
